package j2024.j202407;

import java.util.*;

public class j0708 {
    //692
    public List<String> topKFrequent1(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for(String word:words){
            if(map.get(word) == null){
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(minHeap.size()<k){
                minHeap.offer(entry);
            }else{
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) == 0){
                    if(top.getKey().compareTo(entry.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else{
                    if(entry.getValue().compareTo(top.getValue())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp = minHeap.poll();
            list.add(tmp.getKey());
        }
        Collections.reverse(list);
        return list;
    }
    public List<String> topKFrequent(String[] words, int k) {
            HashMap<String,Integer> map = new HashMap<>();
            for(String a:words){
                map.put(a,map.getOrDefault(a,0)+1);
            }

            PriorityQueue<Map.Entry<String,Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                    //频率相同建大根堆
                    if(o1.getValue().compareTo(o2.getValue())==0){
                        return o2.getKey().compareTo(o1.getKey());
                    }
                    //不同则小根堆
                    return o1.getValue().compareTo(o2.getValue());
                }
            });
            for(Map.Entry<String,Integer> s:map.entrySet()){
                if(heap.size()<k){
                    heap.offer(s);
                }else {
                    Map.Entry<String,Integer> one = heap.peek();
                    //判断字典序建大堆
                    if(one.getValue().compareTo(s.getValue())==0){
                        if(one.getKey().compareTo(s.getKey())>0){
                            heap.poll();
                            heap.offer(s);
                        }
                    }else {
                        if(s.getValue().compareTo(one.getValue())>0){
                            heap.poll();
                            heap.offer(s);
                        }

                    }
                }
            }
            List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> ret = heap.poll();
            list.add(ret.getKey());
        }
        Collections.reverse(list);
        return list;

    }
}
